单链表
// head存储链表头下标，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
//如果为空链表，head=-1，如果有数插入成为表头那么head为表头元素在e[]中的下标

// 初始化 
void init()
{
    head = -1;//-1表示空集 
    idx = 0;//下标从0号点开始
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;//先插入数字指向原来的链表头，然后新的头指针指向插入的数
}
//head=idx,idx++;	 


// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}
 
// 在链表k位置后面插入一个数x
void add(int k,int x){
	e[idx]=x;
	ne[idx]=ne[k];
	ne[k]=idx;
	idx++;
}

//将下标是k点后面的一个点删去
void remove(int k){
	ne[k]=ne[ne[k]];
}

//遍历链表
for(int i=head;i!=-1;i=ne[i]) cout <<e[i]<<endl;


双向链表的模板
//采用数组模拟链表的好处是可以O(1)查询元素，插入元素在数组中位置可任意，因为只要改变指针即可，插入元素x在a[x]的位置
//比如插入的第i个元素为i，那么数组a[i]即为对应元素
/*
#include<bits/stdc++.h>
using namespace std;
#define N 10000005
int n,m,x;
char c[5];
struct node {
    int next,last,v,b;//v为元素被删除的懒标记，只有该元素被遍历到时才删除
    //b表示属于维护的两个链表中的哪一个
}a[N];
struct A {//维护两个链表插入的头尾以及个数，左右插入左右弹出左右删除
    int _size,_start,_end;
    inline void insertl(int x) {
        if (_start) a[_start].last=x;
        a[x].next=_start;
        a[x].last=0;
        _start=x;
        if (!_end) _end=x;
        _size++;
    }
    inline void insertr(int x) {
        if (_end) a[_end].next=x;
        a[x].last=_end;
        a[x].next=0;
        _end=x;
        if (!_start) _start=x;
        _size++;
    }
    inline int popl() {//取出左端第一个元素
        if (!_size) return _start=_end=0;
        while (a[_start].v) _start=a[_start].next;
        a[_start].last=0;
        return _start;
    }
    inline int popr() {
        if (!_size) return _start=_end=0;
        while (a[_end].v) _end=a[_end].last;
        a[_end].next=0;
        return _end;
    }
    inline void remover() {//删除左端的一个元素
        _size--;
        if (!_size) {
            _start=_end=0;
            return ;
        }
        while (a[_end].v) _end=a[_end].last;
        _end=a[_end].last;
        a[_end].next=0;
    }
    inline void removel() {
        _size--;
        if (!_size) {
            _start=_end=0;
            return ;
        }
        while (a[_start].v) _start=a[_start].next;
        _start=a[_start].next;
        a[_start].last=0;
    }
}L,R;
int main() {
    int C=0,D=0;
    scanf("%d",&m);
    int tot=0;
    for (int i=1;i<=m;i++) {
        scanf("%s",c);
        if (c[0]=='L') {
            ++tot;
            a[tot].b=1;
            L.insertl(tot);
        }
        else if (c[0]=='R') {
            ++tot;
            a[tot].b=2;
            R.insertr(tot);
        }
        else if (c[0]=='G') {
            int x;
            scanf("%d",&x);
            if (a[x].b==1) L._size--;
            else R._size--;
            a[x].v=1;
            C++;
        }
        else {
            printf("%d\n",R.popl());
            D++;
        }
        if (L._size>R._size) {
            int x=L.popr();
            L.remover();
            a[x].b=2;
            R.insertl(x);
        }
        else if (R._size-1>L._size) {
            int x=R.popl();
            R.removel();
            a[x].b=1;
            L.insertr(x);
        }
    }
    assert(C<=1500000);
    assert(D<=1500000);
    //cout<<C<<' '<<D<<_endl;
}
*/

双链表
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

优先队列模拟栈
/*栈的特点是后进先出，那用最小队列的话，进栈的时候，数据设置优先级属性，并且这个属性值递减的。
因此优先级就是最大的，这样出队的时候就是把优先级队列最大的元素出队了*/
这种做法的好处是便于合并两个栈，只需要对于入栈的总时间顺序设定优先级即可

栈
// tt表示栈顶的下标 
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}


队列
1. 普通队列：
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}
2. 循环队列
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt)
{

}
//循环队列出现的原因：顺序队列出队后的空间不能再次利用，造成资源浪费。所以出现循环队列
//（1）队列初始化时，front和rear值都为零；
//（2）当队列不为空时，front指向队列的第一个元素，rear指向队列最后一个元素的下一个位置；
//（3）当队列为空时，front与rear的值相等，但不一定为零；

/*
题目大意：给定n个数字，给定3个栈，如何操作我们可以使得所有数据在第一个栈中以非递减的形式存在

解题思路：我们对于给定一些数字可以进行这样一个操作，按这一个数位中是否是1然后把他放入stack2 或者stack3，保证stack2、stack3也是排好序的
从低位1开始向高位
因为在这一位上是1的，那么他相对这一位数值上是0的数字就要更大一些，那我们每次都进行这样的操作，并且按照栈的方式把他扔进原栈中
最后就能够排序成功，而且我们对于每个数字都是需要离散化的（只需要记录其相应的数字位置）
然后对于每个数字我们最多进行操纵10次，最多肯定不会超过20000次
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
pair<int,int> p[maxn];
int ans[maxn][10];
int a[maxn];
int b[maxn];
int c[maxn];
int na,nb,nc;
int n;
int ansn;
void add(int x,int y)
{
    ans[++ansn][0] = x;
    ans[ansn][1] = y;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;++i)
    {
        scanf("%d",&a[i]);
        p[i] = make_pair(a[i],i);
    }
    sort(p + 1,p + 1 + n);
    for(int i = 1;i <= n;++i) a[p[i].second] = i;
    
    for(int i = 0;i < 10;++i)
    {
        na = 0,nb = 0,nc = 0;
        for(int j = n;j >= 1;j--)
        {
            if((a[j] >> i) & 1)
            {
                b[++nb] = a[j];
                add(1,2);
            }
            else
            {
                c[++nc] = a[j];
                add(1,3);
            }
        }
        while(nb)
        {
            a[++na] = b[nb--];
            add(2,1);
        }
        while(nc) 
        {
            a[++na] = c[nc--];
            add(3,1);
        }
    }
    printf("%d\n",ansn);
    for(int i = 1;i <= ansn;++i)
    {
        printf("%d %d\n",ans[i][0],ans[i][1]);
    }
    return 0;
}

单调栈 时间复杂度O(n)
常见模型：找出每个数左/右边离它最近的比它大/小的数，一般题目都需要左右两边各使用一次单调栈
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

//处理好边界：h[0]=-1/h[n+1]=-1;高度置为-1，这样栈时刻不会空，可以省略栈中是否有元素的判断条件tt >= 0
//q[0]=0/q[0]=n+1,;(当h的值大于等于0时)

具体实现：//stk栈第二次使用时不需要重置，只需要将tt=0，以及改变栈顶即可
int stk[N],tt;
for(int i=0;i<n;i++){
    int x;
    cin >>x;
    while(tt && stk[tt] >=x) tt--;//如果栈不为空而且栈顶元素大于等于x，那么就可以删除
    if(tt) cout <<stk[tt]<<endl;//数左边离它最近的比它小的数的下标-tt
    else cout <<-1<<endl;
    stk[ ++tt]=x;//将新的元素插入栈
}

//AcWing 131. 直方图中最大的矩形 上边界确定，需要得到左右两边离它最近的比它小的的边界，包围的就是该上边界最大面积
//应用在h数组中求各元素左右两边离它最近的比它小的数
h[0] = h[n + 1] = -1;

int tt = 0;
q[0] = 0;
for (int i = 1; i <= n; i ++ )
{
    while (h[q[tt]] >= h[i]) tt -- ;
    l[i] = q[tt];
    q[ ++ tt] = i;
}
tt = 0;
q[0] = n + 1;
for (int i = n; i; i -- )
{
    while (h[q[tt]] >= h[i]) tt -- ;
    r[i] = q[tt];
    q[ ++ tt] = i;
}


/*
1-2n中查询[i,i + n - 1]的最小值，需要对i进行反向遍历
*/
单调队列//队列中元素值单调
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ; // hh <= tt
    q[ ++ tt] = i;
}

//滑动窗口求最小值,该队列的首元素总是原队列的最小值
int a[N],q[N];//a为输入的序列，q为维护的队列,q存储的是元素在a中下标
int hh,tt//分别对应对头，队尾
for(int i=0;i<n;i++) cin >>a[i];
for(int i=0;i<n;i++){
    if(hh<=tt && i-k+1 > q[hh]) hh++;
    while(hh<=tt && a[q[tt]]>= a[i]) tt--;//while hh<=tt a[q[tt]]
    q[++tt]=i;
    if(i>=k-1) cout <<a[q[hh]];
}

//维护两个单调队列（一个最大值、一个最小值）,左端点固定满足条件的最小右端点区间
//条件区间最大值-区间最小值大于k
j=1;
h1 = h2 = t1 = t2 = 1;
q1[1] = q2[1] = 1;
for (int i = 1; i <= n; ++i) {
    if (q1[h1] < i) ++h1;//最小值位置小于左端点则弹出
    if (q2[h2] < i) ++h2;
    while (j < i || a[q2[h2]] - a[q1[h1]] <= k) {
        if (j == n)break;
        ++j;
        while (t1 >= h1 && a[q1[t1]] > a[j])--t1;
        while (t2 >= h2 && a[q2[t2]] < a[j])--t2;
        q1[++t1] = j;
        q2[++t2] = j;
    }
    if (a[q2[h2]] - a[q1[h1]] <= k) break;
    ans += n - j + 1;
}


KMP
kmp 判断循环节以及求解循环周期
定理：假设 S 的长度为 len ，则 S 存在最小循环节，循环节的长度 L 为 len – next [ len ]
如果 len 可以被 len - next [ len ] 整除，则表明字符串 S 可以完全由循环节循环组成，循环周期 T = len / L
    
//一个应用，求一个字符串最少在后面加几个字符可以变成回文串
/*
题意可抽象为求字符串后缀的最长回文串，最长的后缀=该后缀的前缀
假设字符串为A，翻转之后的字符串为B，B为模式串，A为主串，利用KMP匹配到主串最后一个元素时的j

hash的做法:
对字符串进行顺序Hash和逆序Hash，然后去枚举位置，如果此时顺序的Hash和逆序的Hash值想等就说明此时是一个回文串
*/

/*
求n个串的最长连续公共子串。可以用后缀数组解。不过还是可以用kmp求解
枚举最短的那个串s的所有后缀，用每个后缀去匹配其他的n-1个串，若对于第i个后缀，
对于其他的n-1个串最长能匹配该后缀到a1,a2```an-1的位置，
则可知第i个后缀的长度为min(a1,a2```an）的前缀是这n个串的公共子串。
*/

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度,下标从1开始，m需要远小于n
//可以理解为判断子串是否含有相同的前后缀，相当于自己匹配自己
//ne[i]表示从p[i]结尾的后缀能够匹配的从p[1]开始的非平凡前缀的最大长度
求模式串的Next数组：//ne[1]=0；所以从i=2开始
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    //此处判断j是否为0的原因在于，如果回跳到第一个字符就不用回跳了
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;//记录一下
}
//ne[1]=0,如果第一个字符匹配失败就从第0个开始，不需要计算

// 匹配，当不匹配时j=ne[j]不断递归回退，直到可以匹配（s[i] == p[j + 1]）
// j可以理解为当前已经匹配完的模式串的最后一位的位置
for (int i = 1, j = 0; i <= n; i ++ )//与s[i]匹配的是p[j+1],所以j=0
{
    while (j && s[i] != p[j + 1]) j = ne[j];//循环条件为j没有退到起点而且不匹配，j=0就是退到起点，第一个元素都不匹配，只能i++
    //如果失配则不断向回跳，直到可以继续匹配
    if (s[i] == p[j + 1]) j ++ ;//防止因为j退到起点，而j++
    if (j == m)
    {
        j = ne[j];
        // 匹配成功j后退一次，重新匹配新的子串，不匹配其他的可以直接break
    }
}
//上面一句的执行结果就是j退回到起点或者是s[i]==p[j+1]匹配上了


AC自动机
/*
给定 n 个长度不超过 50 的由小写英文字母组成的单词，以及一篇长为 m 的文章。
请问，有多少个单词在文章中出现了。
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, S = 55, M = 1000010;

int n;
int tr[N * S][26], cnt[N * S], idx;
char str[M];
int q[N * S], ne[N * S];

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int t = str[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
    }
    cnt[p] ++ ;
}

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 26; i ++ )
        {
            int p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[ ++ tt] = p;
            }
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i ++ )
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str);

        int res = 0;
        for (int i = 0, j = 0; str[i]; i ++ )
        {
            int t = str[i] - 'a';
            j = tr[j][t];//j:表示文本串到i时，模式串匹配到的最深的位置的编号
            //因为ne[]数组的含义,ne[j]位置及ne[ne[j]]...位置都出现过

            int p = j;
            while (p)
            {
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
        }

        printf("%d\n", res);
    }

    return 0;
}

trie图
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=10010,S=55,M=10000010;

int n;
int tr[N*S][26],cnt[N*S],idx;
char str[M];
int q[N*S],ne[N*S];
void insert()
{
    int p = 0;
    for(int i =0;str[i];i++)
    {
        int t = str[i]-'a';
        if(!tr[p][t]) tr[p][t] = ++idx;//如果儿子不存在 创建一个新的节点
        p = tr[p][t];// 沿字符串字母idx继续往下走
    }
    cnt[p] ++;
}
void build()
{
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)//根节点以及第一层结点都是指向根节点，所以直接从第一层开始搜，也就是根的所有儿子开始搜
    {
        if(tr[0][i])
            q[++tt] = tr[0][i];
    }

    while(hh<=tt)
    {
        int t = q[hh++];//队列popleft
        for(int i=0;i<26;i++)
        {
            int p = tr[t][i];//p:自动机中某个第i层结点的idx -> KMP中的i 
            // if(p)
            // {
            //     int j = ne[t];
            //     while(j && !tr[j][i]) j = ne[j];
            //     if(tr[j][i]) j = tr[j][i];
            //     ne[p] = j;
            //     q[++tt] = p;
            // }

            // 优化思路 在没有匹配时 把while循环多次跳 优化为 直接跳到ne指针最终跳到的位置
            // 数学归纳法
            // 假定在循环第i层时，前i-1层都求对了
            // 在第i层没找到字母i,那么去第i-1层父结点t的next指针的位置就是它最终应该跳到的位置
            if(!p) tr[t][i] = tr[ne[t]][i];//ne[t]:j  如果不存在儿子tr[t][i]的话
            // 如果存在儿子节点 则对儿子节点的next指针赋值为tr[ne[t]][i]
            else
            {
                ne[p] = tr[ne[t]][i];
                q[++tt] = p;
            }
        }
    }

}
int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i ++ )
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str);

        int res = 0;
        for (int i = 0, j = 0; str[i]; i ++ )
        {
            int t = str[i] - 'a';
            /*
            while(j && !tr[j][t]) j = ne[j];
            if(tr[j][t]) j=tr[j][t];
            int p = j;
             // she 和 he 的 e结点都有cnt[e]=1
                遍历到she的后缀he的时候 her的相同前缀he肯定是逐层遍历到了的 len(he)<len(she) 逐层遍历
                把所有ne 指针全部加一遍  比如当前p到了she的e  把cnt[p]+进res后 
                把p通过ne[p]跳到he的e 再加上此时指向he中e的p的cnt[p] 
            while(p)
            {
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
            */
            j = tr[j][t];

            int p = j;
            while (p)
            {
                res += cnt[p];
                cnt[p] = 0;//she he 把cnt[e]的用过了之后 res=2 此时再进来一个her 就不能再+he的cnt了,所以cnt[e]用过之后要置0
                p = ne[p];
            }
        }

        printf("%d\n", res);
    }

    return 0;
}

/*
某人读论文，一篇论文是由许多单词组成的。
但他发现一个单词会在论文中出现很多次，现在他想知道每个单词分别在论文中出现多少次
*/
//一个字符串出现的次数=所有满足要求的前缀的个数（该前缀的后缀等于原串）/ 所有的前缀的后缀中某个单词出现的次数
//这不就是ne数组的定义吗:也就是当前单词的后缀可以匹配的最长前缀
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int tr[N][26], f[N], idx;
int q[N], ne[N];
char str[N];
int id[210];

void insert(int x)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int t = str[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
        f[p] ++ ;//记录的是前缀出现的次数
    }
    id[x] = p;
}

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 26; i ++ )
        {
            int &p = tr[t][i];
            if (!p) p = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[ ++ tt] = p;
            }
        }
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )
    {
        scanf("%s", str);
        insert(i);
    }

    build();

    for (int i = idx - 1; i >= 0; i -- ) f[ne[q[i]]] += f[q[i]];//从下往上递推求解

    for (int i = 0; i < n; i ++ ) printf("%d\n", f[id[i]]);

    return 0;
}


Trie树 —— 模板题 
int son[N][26], cnt[N], idx;//idx是当前用到哪个下标

/*插入一个数（int）的二进制形式
01字典树主要用于解决求异或最值的问题，具体为枚举靠右的那个数（插入之前先查询），同时维护字母树（将该数插入），查询前面的数，O(nlogn)
即讨论每一个R，每次R的移动就将pos[R] 插入到字典树中，此时需要找一个满足条件的L
const int N=1e5+5,M=N*31;//因为一个数需要占31个存储单元
int son[M][2],idx;
同时int pos[M];
void insert(int x) 
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(!son[p][u]) son[p][u]=++idx;
        cnts[son[p][u]]++;//可以记录字典树每个节点存储的次数
        p=son[p][u];
    }
}

int query(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(son[p][!u])
        {
            p=son[p][!u];
        }else
        {
            p=son[p][u];
        }
    }
    return xxx
}

多样例,需要清空idx,son,pos
for(int i=0;i<idx;i++)
{
    son[i][0]=son[i][1]=0;
    pos[i]=-1;
}
idx=0;
*/

// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点,son[i][j]表示第i个节点的一个孩子节点是j
//比如插入abc，插入a的时候将a作为0号节点的孩子，a编号为1，然后插入b作为a的孩子，编号为2，
//插入c作为b的孩子，编号为3，此时字典树中存在了一个以c结尾的单词，用cnt数组存储单词的末尾位置，cnt[3]++
// cnt[]存储以每个节点结尾的单词数量
int pos[N],id;//id表示插入元素的编号，表示以该节点结尾是一个单词
// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;//p这个结点不存在儿子u，那么就创建它
        p = son[p][u];
    }
    cnt[p] ++ ;
    pos[p]=id++;// 记录一下插入的数的下标
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
//查询操作同样简单，同样是从根节点逐步找孩子节点，如果在某个位置失配，
//即son[p][u]为0，说明p节点没有孩子u，比如查询abd，查到b节点后发现b没有孩子d，遂未找到abd这个单词。



并查集//可以用于判断环
//注意p[i]与find(i)是存在不同的,在i进行find()操作按秩合并之前p[i]不是i的祖宗

(1)朴素并查集：//返回x的祖宗结点的过程中包含了路径压缩（回溯的过程中）

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点,O(logn)
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：//合并时需要特判a和b是否相同，如果相同不执行size[find(b)] += size[find(a)];

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合： 操作先后顺序不能颠倒
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);
 
 (3)维护到祖宗节点距离的并查集（带权并查集）：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);//不能写为p[x] = find(p[x]);d[x] += d[p[x]];
            d[x] += d[p[x]];//因为这样第一步之后p[x]就被更改为根节点，那么d[p[x]]值错误
            p[x] = u;//也不能写为d[x] += d[p[x]];p[x] = find(p[x]);，因为只有先进行find()函数之后，d[p[x]]的值才知道
            //综上，所以只能先用u存储find(p[x])的值，进行完d[x] += d[p[x]];后再赋值给p[x]
        }
        return p[x];
    }

    int find(int x)//更便于理解
    {
        if (p[x] == x || p[p[x]] == p[x]) return p[x];
        int r = find(p[x]);//r为祖宗节点
        d[x] += d[p[x]];
        p[x] = r;//x指向祖宗节点
        return r;
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
//只需要，更新 d[find(a)] 的路径，下次计算 d[a] 的路径在下次 “路径压缩” 的时候会被自动计算（这也是为什么这题只能使用路径压缩来做，如果不是路径压缩，那么计算完 d[find(a)]，还要更新 find(a) 所有子节点的路径）
//只需要更新a所在集合的根节点，其他节点在路径压缩时更新

void Union(int a,int b)
{
    int fa=Find(a),fb=Find(b);
    if(fa!=fb)
    {
        f[fa]=fb;
        val[fa]=-val[a]+v+val[b];//表示的是当前点父节点比当前点大的情况，然后合并两个集合
    }
} 

void Union(int a,int b)
{
    int fa=Find(a),fb=Find(b);
    if(fa!=fb)
    {
        f[fa]=fb;
        val[fa]=1;//相当于将新加入的b作为新根，然后将并查集中所有元素加一
    }
} 

堆
//可用于优化多路归并问题,即多列数据从大到小排序,求多列数据的前k大数

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
//下面两个数组是为了实现删除第k个插入元素的操作，存储数组下标与第k个插入的映射 
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
//p：下标 h：堆 ph与hp就是映射的关系
int h[N], ph[N], hp[N], size;//这里的size是关键，当删除堆顶后size变换，down（）函数中也'u*2<=size'

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

//小根堆而言，某个元素变大，应该向树的下方移动，与两个儿子节点的最小值交换
//并且这个最小值雄安与变大的元素值
void down(int u)//O（logn）
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

//某个元素变小，只需要和父节点比较是否需要交换
void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆，不同于O（nlogn）的对于所有元素插入建堆
//完全二叉树的底层是不需要进行down操作的，从倒数第二层n/2开始即可
for (int i = n / 2; i; i -- ) down(i);


一般哈希
(1) 拉链法
    int h[N], e[N], ne[N], idx;//h[N]存储哈希值，其他三个与链表有关

	memset(h,-1,sizeof(h));//预处理，-1表示链表结束

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;//保证为正数
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }
    //让新的ne[idx]指向h[k],再让h[k]指向它

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

(2) 开放寻址法
	//方法就如同是“蹲坑”，在得到哈希值准备在这个位置存储的时候，如果“坑位”被占
	//那么找下一个坑位，如果查询一个数那么先寻找它本来应该在的位置，如果为空就可以存下
    //如果不为空而且值不是自身就往后寻找

    int h[N];//N为题目所需存储数目的二到三倍且为质数
    memset(h,0x3f,sizeof(h));//预处理，表示还没有哈希值存入，数字的设置大于待哈希值的范围即可
    //0x3f稍大于10^9

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;//循环到最后就再循环到开头
        }
        return t;
    }

    int k=find(x);
    h[k]=x;//插入
    if(h[k]!=null) cout <<"存在";//查询，如果存在


以 a / b表示斜率，至于细节问题，统一斜率为0的表示为0/1，斜率不存在表示为1/0，其他情况需要让分数化为最简分数，
并且统一负斜率的负号在分子或分母，至于pair的哈希用一个2e9+7的base（x*base+y）丢进哈希表。
手写哈希，可以解决unorder_map的MLE问题，使用init()初始化减少内存使用
const int maxn = 2e3 + 5;
const int mod = 2333;

struct Hash{
    struct Has{
        int num, nxt; ll h;
    } has[maxn];
    int head[mod], cnt;
    int rub[maxn], top;
    void init(){

        while(top) head[rub[top--]] = 0; cnt = 0;
    }
    void add(ll h){

        int u = h % mod; u = u < 0 ? -u : u;
        for(int i = head[u]; i; i = has[i].nxt){

            if(has[i].h == h) { ++has[i].num; return; }
        }
        rub[++top] = u;
        has[++cnt] = { 1, head[u], h }, head[u] = cnt;
    }
    int get(ll h){

        int u = h % mod; u = u < 0 ? -u : u;
        for(int i = head[u]; i; i = has[i].nxt){

            if(has[i].h == h) return has[i].num;
        }
        return 0;
    }
} hi[maxn];

双进制哈希
using ll = long long;
using PLL = pair<ll,ll>;
constexpr ll mod1 = 1000000007;
constexpr ll mod2 = 998244353;
constexpr int N = 5e5 + 5;

struct Hash_string{
    vector<ll> H, P;
    ll base = 131;
    vector<ll> Hi, Pi;
    ll basei = 137;
    int n;

    Hash_string(string s):n((int)s.size()), H((int)s.size() + 1, 0), P((int)s.size() + 1, 0), Hi((int)s.size() + 1, 0), Pi((int)s.size() + 1, 0) {
        P[0] = 1;
        Pi[0] = 1;
        s = " " + s;
        for (int i = 1; i <= n; i++) {
            H[i] = H[i - 1] * base % mod1 + s[i] - 'a' + 1;
            H[i] %= mod1;
            P[i] = P[i - 1] * base % mod1;
            Hi[i] = Hi[i - 1] * basei % mod2 + s[i] - 'a' + 1;
            Hi[i] %= mod2;
            Pi[i] = Pi[i - 1] * basei % mod2;
        }
    }

    PLL get(int L, int R) {
        return make_pair((H[R] - H[L - 1] * P[R - L + 1] % mod1 + mod1) % mod1, (Hi[R] - Hi[L - 1] * Pi[R - L + 1] % mod2 + mod2) % mod2);
    }
};
应用：
string s;
cin >> s;
int n;
cin >> n;
Hash_string H(s);//文本串哈希
vector<pair<ll, ll>> a(n);
map<pair<ll, ll>, int> M, last;
for (int i = 0 ; i < n; i++) {
    string t;
    cin >> t;
    Hash_string h(t);//模式串哈希
    a[i] = h.get(1, t.size());//下标都是从1开始，哈希值为pair类型
    M[a[i]] = 0;
    last[a[i]] = 0;
}
// cerr << '\n';
for (int i = 1; i <= s.size(); i++) {
    for (int j = 0; j <= 30 && i + j <= s.size(); j++) {
        pair<ll, ll> x = H.get(i, i + j);
        // cerr << "i = " << i << " i + j = " << i + j << " x = " << x << " last[x] = " << last[x] << '\n';
        if (M.count(x) && i + j - last[x] >= j + 1) {
            M[x]++;
            last[x] = i + j;
        }
    }
}


字符串哈希（字符串前缀哈希法）//可以做KMP做不了的，除了字符串的循环节
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样h[k]直接用unsigned long long存储，溢出的结果就是取模的结果
//比如"ABCD"就是四位数字1234的p进制数，A对应1，也可以直接用ASCI码，得到的数需要取模
//字母不能映射为0，因为这样"AA"="A"，如果有映射到0就整体加上一个1
//h[0]=0;

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
//可以由公式和前缀哈希值得到所有子串的哈希值

// 初始化
p=131;
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值，已知h[r],h[l-1]
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

长度为n的数列可以哈希为m进制数,0<=a[i]<m,进制哈希
for(int i=1;i<=n;i++)
    hs[i]=hs[i-1]*m+a[i];
还可以进行异或哈希
for(int i=1;i<=m;i++)
    v[i]=rand()*rand();
for(int i=1;i<=n;i++)
    hs[i]=hs[i-1]^v[a[i]];
异或哈希的一些用处：
a^a=0,可以判断元素在子段中出现的奇偶性,hs[l,r]=hs[r]^hs[l-1]
比如比较l-r的子串是否是1-len的一个排列,它的任一一个排列的异或哈希值都相等，所以可以用来判断一个数是否出现过
for(int i=1;i<=n;i++)
    pm[i] = pm[i-1]^(v[i]);
(hs[r]^hs[l-1])==pm[mx]//此处需要括号，因为^优先级低于()

树哈希——P4323 [JSOI2016]独特的树叶
求无根树一个根的哈希值
void dfs0(int x,int pre)
{
    hs[x]=1;
    fa[x]=pre;
    siz[x]=1;
    for(int i=h[x];i;i=ne[i])
    {
        if(e[i]!=pre)
        {
            dfs(e[i],x);
            siz[x]+=siz[e[i]];
            hs[x]+=hs[e[i]]*prm[siz[e[i]]];
        }
    }
}
换根求解其他根的哈希值
void dp(int x,int pre)
{
    for(int i=h[x];i;i=ne[i])
    {
        if(e[i]!=pre)
        {
            int vx=hs[x]-hs[e[i]]*prm[siz[e[i]]];
            hs[e[i]]+=vx*prm[n-siz[e[i]]];
            dp(e[i],x);
        }
    }
}

字符串哈希实现字符串匹配，时间复杂度O（n*m），实现KMP的功能
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const ull has=233;
char s[1234],s2[1234];
ull h[1234],h2[1234];

int main(){

    scanf("%s",s2+1);//辅串
    int len=strlen(s2+1);
    ull l=1;
    for(int i=1;i<=len;i++)
    {
        l*=has;
        h2[i]=h2[i-1]*has+s2[i]-'a';
    }
    l/=has;

    scanf("%s",s+1);//主串
    int len2=strlen(s+1);
    for(int i=1;i<=len;i++)
        h[i]=h[i-1]*has+s[i]-'a';

    for(int i=len+1;i<=len2;i++)
        h[i]=(h[i-1]-l*(s[i-len]-'a'))*has+s[i]-'a';

    for(int i=len;i<=len2;i++)
    {
        if(h2[len]==h[i])
            cout <<i<<endl;
    }

    return 0;
}

中缀表达式转后缀表达式并计算
#include<bits/stdc++.h>
using namespace std;
struct node {
  int op,v;
  char c;
};
queue<node>q;
stack<char>stk;
stack<int>sa;
vector<node>s;
int cg[200];
int gao(){
  int n=s.size();
  for(int i=0;i<n;i++) {
      if(s[i].op==0) {
          q.push(s[i]);
      }else{
          if(s[i].c=='(') {
              stk.push(s[i].c);
          }else if(s[i].c==')') {
              while(stk.size()&&stk.top()!='(') {
                  q.push({1,0,stk.top()});
                  stk.pop();
              }
              if(stk.size()) stk.pop();
         }else if(cg[s[i].c]==2) {
             while(stk.size()&&cg[stk.top()]==2) {
                  q.push({1,0,stk.top()});
                  stk.pop();
              }
              stk.push(s[i].c);
          }else if(cg[s[i].c]==1) {
             while(stk.size()&&cg[stk.top()]) {
                 q.push({1,0,stk.top()});
                  stk.pop();
              }
              stk.push(s[i].c);
          }
      }
  }
  while (!stk.empty()){
      q.push({1,0,stk.top()});
      stk.pop();
  }
  while(!q.empty()) {
      node p=q.front();
      q.pop();
      if(p.op==0) sa.push(p.v);
      else {
          int a=sa.top();
          sa.pop();
          int b=sa.top();
          sa.pop();
          if(p.c=='+') sa.push(b+a);
          if(p.c=='-') sa.push(b-a);
          if(p.c=='*') sa.push(b*a);
          if(p.c=='/') sa.push(b/a);
      }
  }
  return sa.top();
}
int main(){
  //"2*(2+3)-4/(1+1)";
  s.resize(15);
  s[0].op=0,s[0].v=2;
  s[1].op=1,s[1].c='*';
  s[2].op=1,s[2].c='(';
  s[3].op=0,s[3].v=2;
  s[4].op=1,s[4].c='+';
  s[5].op=0,s[5].v=3;
  s[6].op=1,s[6].c=')';
  s[7].op=1,s[7].c='-';
  s[8].op=0,s[8].v=4;
  s[9].op=1,s[9].c='/';
  s[10].op=1,s[10].c='(';
  s[11].op=0,s[11].v=1;
  s[12].op=1,s[12].c='+';
  s[13].op=0,s[13].v=1;
  s[14].op=1,s[14].c=')';
  cg['*']=cg['/']=2;
  cg['+']=cg['-']=1;
  printf("%d\n",gao());
  return 0;
}

//不能解决负数运算，如-2+3
#include<iostream>
#include<unordered_map>
#include<stack>

using namespace std;

//存储运算数 运算符
stack<int> num;
stack<char> op;
//建立映射来判断运算优先级
unordered_map<char, int> cmp = {
    {'+', 1}, {'-', 1} , {'*', 2}, {'/', 2}
};
//模拟一次算术操作
void eval(void){
    int b = num.top();  num.pop();
    int a = num.top();  num.pop();
    char opr = op.top();    op.pop();

    int x;
    if(opr == '+')  x = a + b;
    else if(opr == '-') x = a - b;
    else if(opr == '*') x= a * b;
    else    x = a / b;
    num.push(x);
}

int main(){
    string str;
    cin >> str;

    for(int i = 0; i < str.size(); i++){
        char c = str[i];
        //读入运算数
        if(isdigit(c)){
            int j = i, x = 0;
            while( j < str.size() && isdigit(str[j])){
                //j++ 迭代不能忘 
                x = x *  10 + str[j ++] - '0';
            }
            num.push(x);
            //由于每轮循环有i++,我们需要倒指向最后一个数字
            i = j - 1;
        }else if( c == '(' ){
            //标记一下，括号内数据
            op.push(c);
        }else if( c == ')' ){
            //括号的优先级，先算括号
            while( op.size() && op.top() != '(' )   eval();
            //左括号可以弹出
            op.pop();
        }else{
            //得先把乘除法算了再算加减
            //这里必须得带等于号 我们这题都是正整数计算
            // 0 - 5 + 3 
            //如果不算，上式会被错误计算成 -8
            while( op.size() && cmp[op.top()] >= cmp[c])    eval();
            //压入新运算符
            op.push(c);
        }
    }
    //清理低优先级操作
    while(op.size())    eval();
    cout << num.top() << endl;
    return 0;
}



撤销栈（Undo/Redo Stack）
考虑到有回退操作，利用栈记录所有合法的操作的反操作，当发生回退执行栈顶操作即可。

如果vector<int> ivec中没有元素，ivec.begin()和ivec.end()都是空指针
0个元素的vector,最后一个元素是 ivec[-1]; 第一个元素是 ivec[0];
这个ivec是个空容器，里面没有一个元素，
所以这第一个元素 ivec[0]
不属于空容器ivec
所以 空容器ivec,中 ivec.begin ()== ivec.end()

C++ STL简介
vector, 变长数组，倍增的思想

初始化：
vector<int> q(n);//q中包含n个元素，值为0，下标从0开始
vector<int> q(n,1);//将n个元素初始化为1
二维vector需要指定vector的大小，才可以进行了下标和迭代器访问，如vector<vector<int>> m(M,vector<int>(N));
vec.resize(size)后用push_back，是在vec[size]处开始添加元素，所以resize与push_back不要连用。
resize后，直接通过下标索引的方式改变元素值。

    vector 上的常见操作复杂度（效率）如下：
    随机访问——常数 O(1)
    在末尾插入或移除元素——均摊常数 O(1)
    插入或移除元素——与到 vector 结尾的距离成线性 O(n)

    size()  返回元素个数
    empty()  返回是否为空//是否为空，为空返回true，这个以及上面的所有容器都有，时间复杂度O（1）
    clear()  清空//调用clear之后, vector的尺寸(size)将变成zero. 但它的容量(capacity)却并不发生变化, vector本身并不释放任何内存
//myvector.clear()；myvector.shrink_to_fit();
vector在clear后还需要进行shrink_to_fit否则相当于你释放了个假的空间 
    使用resize()可以改变容量
    front()/back()//访问第一个/最后一个元素
    push_back()/pop_back()//分别为在最后添加/删除一个元素
//往vector中插入pair，需要用到make_pair 不可以单独对first、second赋值
二分查找:lower_bound(q.begin(),q.end(),n)-q.begin(),不是q.lower_bound(...)没有此派生函数
//需要注意的是lower_bound(q,q+cnt,n)-q,如果没有找到会返回q[cnt],此时的q[cnt]可能是有值的，但不在查询区间范围
//所有用数组/vector使用二分查询函数时需要先判断结果的下标是否在查询范围

    指定位置的插入与删除
    //在最前面的元素前插入8,返回新数据的位置
    v.insert(v.begin(),8);
    //在第二个元素前插入新元素1
    v.insert(v.begin()+2,1);
    //在末尾插入新元素3
    v.insert(v.end(),3);
    //删除单个元素，从0开始计数，删除第二个元素,返回下一个数据的位置
    v.erase(v.begin()+2); 
    //删除一段元素，删除迭代器第一到第五区间所有元素
    v.erase(v.begin()+1,v.begin()+5); 

    begin()/end()
    []
    支持比较运算，按字典序
    /*vecot <int> a(4,3),b(3,4);
    if(a<b)  puts("a<b");*/

/*
resize()的作用是改变vector中元素的数目。

如果n比当前的vector元素数目要小，vector的容量要缩减到resize的第一个参数大小，即n。并移除那些超出n的元素同时销毁他们。

如果n比当前vector元素数目要大，在vector的末尾扩展需要的元素数目，如果第二个参数val指定了，扩展的新元素初始化为val的副本，否则按类型默认初始化。

注意：如果n大于当前的vector的容量(是容量，并非vector的size)，将会引起自动内存分配。所以现有的pointer,references,iterators将会失效。
*/

advance(it,n); 将迭代器移动到指定位置
//前进迭代器 it n 次，或直至抵达 bound ，先到为止 ,迭代器++而不是+1
list 是支持常数时间从容器任何位置插入和移除元素的容器。不支持快速随机访问。它通常实现为双向链表
在 list 内或在数个 list 间添加、移除和移动元素不会非法化迭代器或引用。迭代器仅在对应元素被删除时非法化。
在vector的基础上增加了
    push_front()
      插入元素到容器起始
    pop_front()
      移除首元素 

    reverse()
      将该链表的所有元素的顺序反转
    unique()
      删除连续的重复元素
    sort()
      对元素进行排序 

    auto result1 = std::find(std::begin(v), std::end(v), n1);
    查找

pair<int, int>//两个变量的结构体
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
    /*pair<int ,string> p;
    p=make_pair(10,"yxc");
    p={20."abc"};*/
    //也可由存储三个：pair<int,pair<int ,int>>p;

string，字符串（元素类型为char）
//用来dfs，是因为有一些与数字相关的函数
    size()/length()  返回字符串长度，返回类型不是int，需要强制转换
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串//下标从0开始，没有子串长度变量就是输出起始下标后面所有的
    c_str()  返回字符串所在字符数组的起始地址
    //输出时printf("%s",a.c_str());

    string str=“world”;
    const char *p = str.c_str();//同上，要加const或者等号右边用char*
    
    char[]转string : 这里可以直接赋值。
    string转char[] ： 下标直接访问，所以用一个循环就可以赋值

    str+=str2//在str后增加str2，（string类型）还可以+=（char类型）
    //在字符串的前面加上一个字符 str='x'+str;
    find(待查找的元素) //元素的下标
    //s.npos 如果没找到，返回一个特别的标志c++中用npos表示
    to_string()函数//将数值转化为字符串。返回对应的字符串，支持int,long long,double
    pop_back()//删除最后一个元素
//输入需要用cin
//如果用scanf 先读进字符数组 再将字符数组赋给string
//cin >>s,s = " " + s; 字符下标从1开始


erase函数的原型如下：
（1）string& erase ( size_t pos = 0, size_t n = npos );
（2）iterator erase ( iterator position );
（3）iterator erase ( iterator first, iterator last );
也就是说有三种用法：
（1）erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
（2）erase(position);删除position处的一个字符(position是个string类型的迭代器)
（3）erase(first,last);删除从first到last之间的字符（first和last都是迭代器）

// 第(1)种用法
str.erase (10,8);
cout << str << endl;        

// 第(2)种用法
it=str.begin()+9;
str.erase (it);
cout << str << endl;   

// 第(3)种用法
str.erase (str.begin()+5, str.end()-7);
cout << str << endl;   

queue, 队列//无法查询队列除队头队尾的元素
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素
    /*queue <int > q;
    q=queue<int>();
    清空方法：重新构造*/

//可以求序列前缀长度大于等于k的前k小数的和，只需要维护一个小根堆即可
priority_queue, 优先队列，默认是大根堆
    push()  插入一个元素
    top()  返回堆顶元素//注意
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;//PII 也适用
    //改为小根堆的两种方法：一是priority_queue<int,vector<int>,greater<int>>heap;
    //二是q.push(-x);

priority_queue< Node, vector<Node>, cmp1> q1;
weight大的优先级高//注意return处的大于小于符号与sort的相反
struct cmp1
{
    bool operator () (const Node &a, const Node &b)       
    {
        return a.weight < b.weight;         
    }
};

另一种写法：
priority_queue<Node2> q3;
struct Node2 
{
    char data;
    int weight;
    Node2(char _data, int _weight)
    {
        data = _data;
        weight = _weight;
    }
    friend bool operator < (const Node2 &a,const Node2 &b)
    {
        return a.weight < b.weight;//注意只重载小于号,不要去重载大于号         
    } 
};



stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素//栈空的时候调用top函数会段错误,一定要先保证栈不为空,这条也适用queue
    pop()  弹出栈顶元素

deque, 双端队列，对头对尾均可以插入删除，可以下标访问,"加强的vector"，但是速度慢
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
//定义map时，用greater< Key>实现按Key值递减插入数据 multimap<int,int,greater<int> >mp;
//注意<int>后空一格
类型可以为结构体，不过在结构体中需要同优先队列一样定义排序规则
如果不在结构体里面定义排序规则那么就需要向下面一样写一个函数对象
/*
struct cmp{
    bool operator() (pll a, pll b) {
        return a.fi > b.fi;
    }
};
set<pll, cmp> s[2]; //同理map
*/

//map<typename A, typename B>的形式，map的内部实现默认使用A类型变量的升序来排序map的值。
//可以自定义排序规则,不过也可以将map中元素导入到vector中进行排序
/*
vector<pair<string, int>> a;
map<string, int>        m;

for(auto &i : m) {
        a.push_back(make_pair(i.first, i.second));q
    }
sort(a.begin(), a.end(), cmp);

bool cmp(pair<string, int> x, pair<string, int> y) {
    if(x.second == y.second)
        return x.first < y.first;
    return x.second > y.second;
}*/
/*for (set<int>::iterator iter = st.begin(); iter != st.end(); ++iter) {
    //操作数*iter
}*/

    size() O(1)
    empty() O(1)
    clear() O(n)
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset//一般将set作为平衡树使用
        insert()  插入一个数
        find()  查找一个数//不存在返回end（）迭代器
        count()  返回某一个数的个数//set中O(logn) multiset中不一定为O(logn)
        erase() 
            (1) 输入是一个数x，删除所有x   O(k + logn)//如果set是pair类型那么输入的也需要是pair类型，不能是first/second
            //返回值为一个整数，表示成功删除的元素个数
            (2) 输入一个迭代器，删除这个迭代器//返回值都是迭代器，其指向的是 set 容器中删除元素之后的第一个元素。
        lower_bound()/upper_bound()//找不到返回end（）迭代器
            lower_bound(x)  返回大于等于x的最小的数的迭代器//结果为：*s1.lower_bound(n) 返回的是迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器//通过迭代器的加减可以访问前面/后面的元素
        找小于等于x的最大的数:可以将所有数取反,然后使用lower_bound()
/*
同时维护升降序的两个 std::set，插入时同时插入，删除时同时删除，关于边界处理可以在末尾添加哨兵解决
查找前驱时可以在升序的 std::set 里 std::upper_bound；
查找后继时可以在降序的 std::set 里 std::upper_bound。
*/
简单应用,查询[L,R]中满足条件的数，存储在set中，并从后往前访问
ps.从后往前找需要特殊判断set为空的情况，此时二分查找函数返回x.end()，如果访问会造成RE的情况

while(...){
    auto it=s.upper_bound(r);
    if(it==s.begin())
        break;
    --it;
    if(*it<l)
        break;
    s.erase(it);
}

    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)，可以用count()  返回某一个数的个数
        //count()更快，因为[]会插入
        lower_bound()/upper_bound()
        //二分查找函数，先比较的是第一关键字，然后是第二关键字，从小到大
        //然后返回值的迭代器可以直接使用,比如It->first
    可以map<string,int> mp; char s[10]="abc"; mp[s]=1; 不过字符串长时相较与哈希慢
//支持map<pair<int,int>,int> 不支持unorder_map<pair<int,int>,int> 
//可以将一个坐标映射成一个编号

     //#include<unordered_set>
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    //unorder_map时不要用insert插入,而是用[]更快
    和上面类似，支持[]（没有被插入值first其second为0）,增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--
    reserve()//为至少为指定数量的元素预留存储空间。这会重新生成哈希表。
 关于哈希表卡常：unordered_map开在全局,然后每次使用不clear(),而是reserve(50000) 个人使用中存在问题


手写hash降低常数
const int maxsz=4e6+9;//@素数表@:1e7+19,2e7+3,3e7+23
//1e6+3,2e6+3,3e6+7,4e6+9,1e5+3,2e5+3,3e5+7,4e5+9
//@要保证取值的操作次数小于maxsz,maxsz最好为素数@
//@count操作不增加新节点@
class hash_map{public:
  struct node{ll u;int v,next;}e[maxsz<<1];
  int head[maxsz],nume,numk,id[maxsz];
  bool count(ll u){
    int hs=u%maxsz;
    for(int i=head[hs];i;i=e[i].next)
      if(e[i].u==u) return 1;
    return 0;
  }
  int& operator[](ll u){
    int hs=u%maxsz;
    for(int i=head[hs];i;i=e[i].next)
      if(e[i].u==u) return e[i].v;
    if(!head[hs])id[++numk]=hs;
    return e[++nume]=(node){u,0,head[hs]},head[hs]=nume,e[nume].v;
  }
  void clear(){
    rep(i,0,numk)head[id[i]]=0;
    numk=nume=0;
  }
};
hash_map mp;//定义


//可以比bool数组省八倍内存，bool一个元素八位，而一个一位二进制数一个位
//应用场景比如存储10000*10000的bool数组
bitset, 圧位//bitset<UP> f[N]; 可以用来优化dp状态转移，适用于第二维只有0/1的情况
    bitset<10000> s;//bitset<N>a, b; 异或非左右移的复杂度为O(N)，常数为1/32 
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反


STL中的函数random_shuffle()用来对一个元素序列进行随机排列//与 first 和 last 间的距离成线性。
random_shuffle(a, a + 5);与srand()结合一起使用以提高结果的随机性。因为默认情况下，rand()的初始种子是确定的，而srand()可以改变初始种子
一些不常用函数的汇总：
isdigit(),isalpha()//检查所传的字符是否是数字或者字母
tolower() //把给定的字母转换为小写字母,返回值就是小写字母
cout <<'\t'<<'\n' //c++输出的制表符以及换行
for(int i = 1; i <= n; i++) cout << arr[i] << " \n"[i == n];//最后一行无空格
__gcd(a,b) 注意两个-
nth_element()函数
//nth_element的作用就是在Θ ( n ) 的时间复杂度内使得给定位置上的值成为这个位置该有的值
（特殊的，在比较符号为小于并且起始位置为1的时候，做的是将数组中第n大的数放在n号位置）
nth_element(a+1,a+n,a+m+1,cmp);
数组a[]的第1~m个位置有数，现在要求第n大
int __builtin_popcount (unsigned int x)//返回二进制表示中1的个数
assert() 的用法很简单，我们只要传入一个表达式，它会计算这个表达式的结果：如果表达式的结果为“假”，assert() 会打印出断言失败的信息，并调用 abort() 函数终止程序的执行；
如果表达式的结果为“真”，assert() 就什么也不做，程序继续往后执行。
#pragma comment(linker, "/STACK:10240000000,10240000000")//扩栈

strtok函数
int in=0;
char buffer[20] = "Fred,John,Ann";
char *p[3];
char *buf = buffer;
while((p[in] = strtok(buf, ",")) != NULL) {
    in++;
    buf = NULL;
}

atoi()和stoi()
相同点：
①都是C++的字符处理函数，把数字字符串转换成int输出
②头文件都是#include<cstring>
不同点：
①atoi()的参数是 const char* ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char*类型的
而stoi()的参数是const string*,不需要转化为 const char*；
stoi()会做范围检查，默认范围是在int的范围内的，如果超出范围的话则会runtime error

make_heap(), pop_heap(), push_heap()用法

make_heap()是生成一个堆，大顶堆或小顶堆
make_heap(_RAIter,_RAIter) 默认生成大顶堆
make_heap(_RAIter,_RAIter,_Compare) _Compare有两种参数，一种是greater（生成小顶堆），一种是less（生成大顶堆）

vector <int> v1;
pop_heap(v1.begin(),v1.begin()+kk,less<int>() );//STL中的容器指示位置需要begin(),end()


push_heap()是向堆中插入一个元素，并且使堆的规则依然成立
push_heap(_RAIter,_RAIter) 默认为大顶堆
push_heap(_RAIter,_RAIter,_Compare) _Compare有两种参数，一种是greater（小顶堆），一种是less（大顶堆）
调用push_heap之前必须调用make_heap创建一个堆
首先数组push_back插入元素，然后再调用push_heap，它会使最后一个元素插到合适位置
注意，push_heap中的_Compare和make_heap中的_Compare参数必须是一致的，不然会插入堆失败，最后一个元素还是在最后位置，导致插入失败

pop_heap()是在堆的基础上，弹出堆顶元素。
pop_heap(_RAIter,_RAIter) 默认为大顶堆
pop_heap(_RAIter,_RAIter,_Compare) _Compare有两种参数，一种是greater（小顶堆），一种是less（大顶堆）
比如pop_heap(nums.begin(), nums.end(),greater<int>())，它会将堆顶元素（即为数组第一个位置）和数组最后一个位置对调，然后你可以调用数组pop_back，删除这个元素
注意，pop_heap中的_Compare和make_heap中的_Compare参数必须是一致的，不然会失败

卡常技巧：
1.++i快于i++
//2.int data(5)快于int data=5
3.取模非常慢，所以尽量用减法代替
//4.for(int i=1;i<=n;i++)===>for(register int i=1;i<=n;i++)（快到飞起）
//5.int add(int x,int y){return x+y;}=> inline int add(int x,int y){return x+y;}
6.减少使用STL，他们的常数非常大
7.define比赋值要快
8.定义数组大小时尽量使用奇数
9.尽量不要用bool，int是最快的
10.if() else语句比()?():()语句要慢，逗号运算符比分号运算符要快。
11.位运算相对于整数运算是很快的,也就是说,如果某些运算可以由位运算代替,你的程序就会快很多，比如说奇偶数判断 num&1
12.long long 数组 慢于 int 数组，所以有的地方没必要开long long 就不要开，能用int就别用long long
13.尽力减少除法运算，乘法运算快除法运算3-5倍 
14.memset 慢于 for
15.避免重复定义变量,如
// for(register int iii=1;iii<=m;iii++){
//     int cnt=get();
16.少写头文件，函数能手打就手打，比如手写了max：#define max(x,y) ((x)^(((x)^(y))&(-((x)<(y)))))

//#define debug(x) cout<<#x<<" x:"<<x<<endl


